package com.xuwei.base.sort;
/**
 * 二分排序
 * @author xuwei
 *
 */
public class BinarySort {
	
	public static void sort(int[] arr){
		for(int i=1;i<arr.length;i++){
			int left= 0;
			int right= i-1;
			int pivot = (left+right)/2;
			while(left<right){
				while(left<right){
					if(arr[pivot]>arr[i]){
						right = pivot-1;
						pivot = (left+right)/2;
					}else{
						break;
					}
				}
				while(left<right){
					if(arr[pivot]<arr[i]){
						left = pivot+1;
						pivot = (left+right)/2;
					}else{
						break;
					}
				}
			}
			if(left>=right){
				if(arr[pivot]<arr[i]){
					pivot++;
				}
				int j = i;
				int k = j-1;
				while(k>=pivot){
					int tmp = arr[j];
					arr[j] = arr[k];
					arr[k] = tmp;
					j--;
					k--;
				}
			}
		}
	}
	
	

}
